package q1981_minimizeTheDifference;

public class Solution_2 {
    /*
    solution1用的dfs，这里可以理解为直接通过迭代解决
    这种方式的好处在于不用排序
     */
    public int minimizeTheDifference(int[][] mat, int target) {
        int m = mat.length, n = mat[0].length;
        boolean[] set = new boolean[4901];
        for (int i = 0; i < n; i++) {
            set[mat[0][i]] = true;
        }
        for (int i = 1; i < m; i++) {
            boolean[] cur = new boolean[4901];
            for (int k = 0; k < 4901; k++) {
                if (set[k]) {
                    for (int j = 0; j < n; j++) {
                        int num = mat[i][j];
                        if (num + k < 4901) cur[num + k] = true;
                    }
                }

            }
            set = cur;
        }
        int ans = Integer.MAX_VALUE;
        for (int k = 0; k < 4901; k++) {
            if (set[k]) {
                ans = Math.min(ans, Math.abs(k - target));
            }
        }
        return ans;
    }
}
